package com.example.stack;

import java.sql.SQLOutput;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。
 *  请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。
 *  此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。
 *  进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
 *
 *  当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.
 *
 *  示例1:
 *   输入：
 * ["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
 * [[1], [1], [2], [1], [], []]
 *  输出：
 * [null, null, null, 2, 1, -1]
 *
 *  示例2:
 *   输入：
 * ["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
 * [[2], [1], [2], [3], [0], [0], [0]]
 *  输出：
 * [null, null, null, null, 2, 1, 3]
 */
public class Interview03_03_StackOfPlates {
    public static void main(String[] args) {
        StackOfPlates stackOfPlates = new StackOfPlates(1);
        stackOfPlates.push(1);
        stackOfPlates.push(2);
        System.out.println(stackOfPlates.popAt(1));
        System.out.println(stackOfPlates.pop());
        System.out.println(stackOfPlates.pop());
//        stackOfPlates = new StackOfPlates(2);
//        stackOfPlates.push(1);
//        stackOfPlates.push(2);
//        stackOfPlates.push(3);
//        System.out.println(stackOfPlates.popAt(0));
//        System.out.println(stackOfPlates.popAt(0));
//        System.out.println(stackOfPlates.popAt(0));


    }

    static class StackOfPlates {
        private int curStackIndex; // 记录当前栈的数量
        private List<Deque<Integer>> stacks;
        private int singleSize;

        public StackOfPlates(int cap) {
            stacks = new LinkedList<>();
            curStackIndex = 0;
            stacks.add(new LinkedList());
            singleSize = cap;
        }

        public void push(int val) {
            if (singleSize <= 0) {
                return;
            }
            if (curStackIndex >= 0) {
                Deque<Integer> tmpStack = stacks.get(curStackIndex);
                if (tmpStack.size() < singleSize) { // 最后一个栈未满
                    tmpStack.push(val);
                } else {
                    stacks.add(new LinkedList());
                    stacks.get(++curStackIndex).push(val);
                }
            } else {
                stacks.add(new LinkedList());
                stacks.get(++curStackIndex).push(val);
            }
        }

        public int pop() {
            if (curStackIndex >= 0) {
                Deque<Integer> tmpStack = stacks.get(curStackIndex);
                if (tmpStack != null && tmpStack.size() > 0) { // 最后一个栈还有元素时
                    int tmp = tmpStack.pop();
                    if (tmpStack.size() == 0) { // 本次pop后最后一个栈为空了,需要将最后该栈移除
                        stacks.remove(curStackIndex--);
                    }
                    return tmp;
                }

                return -1;

            }

            return -1;
        }

        public int popAt(int index) {
            if (curStackIndex >= index && index >= 0) {
                Deque<Integer> tmpStack = stacks.get(index);
                if (tmpStack != null && tmpStack.size() > 0) {
                    int tmp = tmpStack.pop();
                    if (tmpStack.size() == 0) {
                        stacks.remove(index);
                        curStackIndex--;
                    }

                    return tmp;
                }

                return -1;
            }
            return -1;
        }
    }
}
